package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 143. 重排链表
 * @date 2025/6/4 11:04
 */
public class E143 {

    /**
     * 方法一：结合栈实现
     *
     * @param head 链表头结点
     */
    public void reorderList1(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        curr = head;
        int halfSize = stack.size() >> 1;
        for (int i = 0; i < halfSize; i++) {
            ListNode next = curr.next;
            ListNode pop = stack.pop();
            curr.next = pop;
            pop.next = next;
            curr = next;
        }
        if (curr != null) {
            curr.next = null;
        }
    }

    /**
     * 方法二：拆成两个链表，再合并
     *
     * @param head 链表头结点
     */
    public void reorderList2(ListNode head) {
        if (head.next == null) return;
        ListNode l1 = head, l2 = head, prev = null;
        while (l2 != null && l2.next != null) {
            prev = l1;
            l1 = l1.next;
            l2 = l2.next.next;
        }
        prev.next = null;
        l2 = l1;
        l1 = head;
        l2 = reverse(l2);
        head = merge(l1, l2);
    }

    /**
     * 链表翻转
     *
     * @param head 链表头结点
     * @return 翻转后的链表头结点
     */
    private ListNode reverse(ListNode head) {
        ListNode sentinel = new ListNode();
        while (head != null) {
            ListNode temp = head.next;
            head.next = sentinel.next;
            sentinel.next = head;
            head = temp;
        }
        return sentinel.next;
    }

    /**
     * 合并两个链表
     *
     * @param l1 链表1
     * @param l2 链表2
     * @return 合并后的链表头结点
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(), curr = sentinel;
        while (l1 != null && l2 != null) {
            ListNode t1 = l1.next;
            ListNode t2 = l2.next;
            curr.next = l1;
            curr = curr.next;
            curr.next = l2;
            curr = curr.next;
            l1 = t1;
            l2 = t2;
        }
        return sentinel.next;
    }
}
